//99. 恢复二叉搜索树

/**
 * 
 * !!!!!!!!!!!!!树的遍历空间复杂度为O(树的高)
 */




import TreeNode from TreeNode

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    let list = []
    inOrder(root,list)
    let t1 = 0
    let t2 = 0
    let small = false
    for (let i=0 ;i<list.length-1;i++) {
        if(list[i]>list[i+1]){
            if(!small){
                t1 = list[i]
                t2 = list[i+1]
                small = true
            }
            else{
                t2 = list[i+1]
                break
            }
        }

    }
    inOrder(root,list,t1,t2)
};

/**
 *@param {TreeNode} root
 @param {Array} list
 */
let inOrder = (root,list,t1=null,t2=null)=>{
    if(root!=null){
        inOrder(root.left,list,t1,t2)
        if(!t1)list.push(root.val)
        else{
            if(root.val===t2) root.val = t1
            else if(root.val===t1) root.val = t2
        }
        inOrder(root.right,list,t1,t2)
    }
}